package BFS_DFS;

import java.util.Scanner;

/*
在N × N N×NN×N的国际象棋棋盘上放置n个皇后，使得任何一个皇后都无法直接吃掉其他的皇后，
即任意两个皇后都不能处于同一条横行、纵行或斜线上。第一行输入皇后的数量N，输出N个皇在N ∗ N N*NN∗N的棋盘上，
在不吃掉其它皇后的情况下总共的放法种数
 */
public class DFSN皇后 {
    static int count;//皇后的摆法
    static int N;//皇后数量
    static int[] arr;//皇后的位置

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        N=sc.nextInt();
        arr=new int[N];
        placeQueue(0);
        System.out.println(count);
    }

    static void placeQueue(int n){
        if(n==N){
            count++;
            return;
        }
        for (int i = 0; i < N; i++) {
            arr[n]=i;
            if(!isConflict(n)){//未发生冲突，可以继续放下一个皇后
                placeQueue(n+1);
            }
        }
    }

    static boolean isConflict(int n){
        for (int i = 0; i < n; i++) {
            if(arr[i]==arr[n]||Math.abs(i-n)==Math.abs(arr[i]-arr[n])){
                //arr[i]==arr[n]在同一列
                //Math.abs(i-n)==Math.abs(arr[i]-arr[n]在同一斜线
                return true;
            }
        }
        return false;
    }
}

